# Read the Solution [here](https://quastor.org/cracking-the-coding-interview/stacks-and-queues/three-in-one)

# Three in One

## Cracking the Coding Interview (CTCI) 3.1

<br />

## Question

Write a class that mimics three stacks. You can only use a single array as the underlying data structure.

```
Example
a = ThreeStack()
a.push(0, 4) # stack 0, push 4
a.push(1, 5) # stack 1, push 4
a.push(2, 7) # stack 2, push 5
a.push(0, 6) # stack 0, push 6
print(a.pop(0)) # 6
print(a.pop(1)) # 5
print(a.pop(2)) # 7
```

<details>
  <summary>Beginner Solution</summary>

  We can implement our stacks with **fixed** capacity.

  <br />

  Once a stack is filled, a user cannot push more items to it without first popping off items.

  <br />

  We'll implement the stacks using a single array that has a fixed capacity of $$n$$.

  <br />

  The first stack will use elements [0, $$\frac{n}{3}$$).

  <br />

  The second stack will use elements [$$\frac{n}{3}$$, $$\frac{2n}{3}$$).

  <br />

  The third stack will use elements [$$\frac{2n}{3}$$, n).

  <br />

  We will maintain 2 lists of pointers. The first list will keep track of where the tops are for each of the 3 stacks.

  <br />

  The second list will keep track of the limits for each of the three stacks.

  ```python
  class ThreeStack:
      def __init__(self, capacity = 5):
          capacity = capacity * 3 # since we have 3 stacks
          self.items = [None] * capacity
          # pointers for tops of stacks 0, 1, 2
          self.tops = [0, capacity // 3, 2 * (capacity // 3)]
          # pointers for limits of stacks 0, 1, 2
          self.limits = [capacity // 3, 2 * (capacity // 3), capacity]
    
      def push(self, stack, item):
          if stack > 2:
              raise ValueError("stack does not exist")
          
          if self.tops[stack] >= self.limits[stack]:
              raise Exception(f"stack {stack} is full")
          
          self.items[self.tops[stack]] = item
          self.tops[stack] += 1
  
      
      def pop(self, stack):
          if stack > 2:
              raise ValueError("stack does not exist")
          top = self.tops[stack] - 1
          if top < 0 or self.items[top] == None:
              raise IndexError("pop from empty stack")
          
          item = self.items[top]
          self.items[top] = None
          self.tops[stack] = top
  
          return item
  ```

</details>






